/**
 * Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.
 */
package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.List;

public class MultiplyString {
    public String multiply(String num1, String num2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(num1.length() == 0)
    		return num2;
    	else if(num2.length() == 0)
    		return num1;
        else if(num1.equals("0") || num2.equals("0"))
            return "0";
    	
        List<String> can = new ArrayList<String>();
        
        for(int i = num1.length()-1; i >= 0; i--)
        {
            int v1 = num1.charAt(i) - '0';
            String sub = new String("");
            int f = 0;
            for(int j = num2.length()-1; j >= 0; j--)
            {
                int v2 = num2.charAt(j) - '0';
                int res = v1 * v2 + f;
                f = res / 10;
                int r = res % 10;
                sub = r + sub;
            }
            if(f != 0)
            	sub = f + sub;
            can.add(sub);
        }
        
        String res = "";

            int f = 0;
            int i = 0;
            for(;can.size() >= 1;)
            {
                int sum = f;
               
                for(int j = i; j >= 0; j--)
                {
                    String sub = can.get(j);
                    int val = sub.charAt(sub.length()-1) - '0';
                    sum += val;
                    can.remove(j);
                    if(sub.length() > 1)
                        can.add(j, sub.substring(0, sub.length()-1));
                    else
                    	i--;
                }
                int r = sum % 10;
                f = sum / 10;
                res = r + res;
                
                if(i < can.size()-1)
                    i++;
                else
                    i = can.size()-1;
            }
        
        if(f != 0)
           	res = f + res;
            
        return res;
    }
    
    public static void main(String[] args)
    {
    	MultiplyString ms = new MultiplyString();
    	ms.multiply("82978", "75");
    }
}
